/*
 * @lc app=leetcode.cn id=438 lang=swift
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        let sArr = Array(s)
        var need: [Character: Int] = [:]
        var window: [Character: Int] = [:]
        for c in p {
            need[c, default: 0] += 1
        }

        var left = 0, right = 0
        var matchCount = 0
        var result: [Int] = []
        while right < sArr.count {
            let rChar = sArr[right]
            right += 1
            if let rCount = need[rChar] {
                window[rChar, default: 0] += 1
                if window[rChar] == rCount {
                    matchCount += 1
                }
            }

            while matchCount == need.count {
                if right - left == p.count {
                    result.append(left)
                }
                let lChar = sArr[left]
                left += 1
                if let lCount = need[lChar] {
                    if window[lChar] == lCount {
                        matchCount -= 1
                    }
                    window[lChar]! -= 1
                }
            }
        }
        return result
    }
}
// @lc code=end

